[BAEKJOON] 16437. 양 구출 작전

문제 :

N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다.

1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다.

늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.

각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다.

양들은 1번 섬으로 가는 경로로 이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.

얼마나 많은 양이 1번 섬에 도달할 수 있을까요?

입력 :

첫 번째 줄에 섬의 개수 N (2 ≤ N ≤ 123,456) 이 주어집니다.

두 번째 줄부터 N-1개에 줄에 2번 섬부터 N번 섬까지 섬의 정보를 나타내는 ti, ai, pi (1 ≤ ai ≤ 109, 1 ≤ pi ≤ N) 가 주어집니다.

ti가 ’W’ 인 경우 i번 섬에 늑대가 ai마리가 살고 있음을, ti가 ’S‘인 경우 i번 섬에 양이 ai마리가 살고 있음을 의미합니다. pi는 i번째 섬에서 pi번 섬으로 갈 수 있는 다리가 있음을 의미합니다.

출력 :

첫 번째 줄에 구출할 수 있는 양의 수를 출력합니다.

풀이 :

우리학교 알고리즘 대회 Goricon에서 출제된 문제다 보니 난이도가 궁금해서 풀어보게 되었다.

문제 자체는 핵심만 파악하고 자료구조만 잘 이해한다면 접근이 가능했던 문제였다.

각 섬들은 상위 노드에 한 경로로만 연결되있는 구조였다. 정확히 말하자면 트리(tree) 구조를 가지고 있다.

처음에 접근이 잘못됬던 경우에는 루트 노드부터 리프 노드로 향하면서 양이 늑대 누적합보다 클 경우에는 그때마다 양 누적합에 더해주는 식으로 구현하였다.

하지만 이런 경우는 양이 루트 노드로 향할 때 소수끼리 갈라져 들어오는 경우가 되기 때문에 늑대에게 비교적 더 많이 잡아먹히게 된다.

따라서 이 문제의 핵심은 부모 노드로 향할 때 최대한 많은 양들을 한꺼번에 끌어모아 섬을 건너야 한다.

그렇게 구현해야 늑대들이 한번에 잡아먹을 수 있는 양의 수가 한정 되어 있기 때문에 덜 잡아 먹힐 수 있다.

따라서 본 문제는 루트 노드에서 시작하여 리프 노드로 재귀 탐색 후 양의 누적합을 차례로 계산하면 접근이 가능한 문제이다.

코드 :

#include <iostream>
#include <vector>

#define ll long long

using namespace std;
typedef struct Info {
    bool iswolf = false;
    int cnt = 0;
    vector<int> childs;
} Info;
vector<Info> nodevec;
int n;

ll checkSheep(int idx) {
    int size = nodevec[idx].childs.size();
    if (!size) return ((nodevec[idx].iswolf) ? 0 : nodevec[idx].cnt);

    ll sum = 0;
    for (int i = 0; i < size; i++)
        sum += checkSheep(nodevec[idx].childs[i]);
    if (nodevec[idx].iswolf) sum -= nodevec[idx].cnt;
    else sum += nodevec[idx].cnt;
    return ((sum <= 0) ? 0 : sum);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    char input;
    int num, parent, i;
    cin >> n;
    nodevec.resize(n + 1);
    for (i = 2; i <= n; i++) {
        cin >> input >> num >> parent;
        nodevec[parent].childs.push_back(i);
        nodevec[i].cnt = num;
        nodevec[i].iswolf = (input == 'W');
    }
    cout << checkSheep(1) << '\n';
    return 0;
}